package com.notes.algo.exam;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * @author
 * @Describe 一种数据压缩算法实现：将长字符串（称为短语）按数据编码成短小标记，用小标记代替字典中的短语。
 * @date
 */
public class Solution2 {

    public static void main(String[] args) {
        java.util.Scanner sc = new Scanner(System.in);
        while (true) {
            String dicStr = sc.nextLine(); // ABCBCBCBCA / ABBC
            if (dicStr.equals("exit") || dicStr.equals("quit")) {
                System.exit(0);
            }
            List<String> dicR = dicCompress(dicStr);
            dicR.forEach(x -> System.out.println(x));
            String orgDicStr = dicUnCompress(dicR);
            System.out.println(orgDicStr + " " + orgDicStr.equals(dicStr));
        }
    }

    /**
     * 压缩
     *
     * @param dicStr
     * @return
     */
    public static List<String> dicCompress(String dicStr) {
        // System.out.println(dicStr);
        List<String> result = new ArrayList<String>();
        // 窗口最大大小
        // int maxWidow = 10;
        // 字典缓冲区窗口大小
        int hisWindow;
        // 预读缓冲区窗口大小
        int preReadWindow;
        // 长字符串长度
        int length = dicStr.length();
        // 遍历长字符串
        for (int i = 0; i < length; i++) {
            /*if (i + 1 <= maxWidow) {
                hisWindow = i;
            } else {
                hisWindow = maxWidow;
            }*/
            // 字典缓冲区窗口设置为当前的方位位置
            hisWindow = i;
            // 预读缓冲区窗口大小设置，结束边界不能大于长字符串的长度
            if (i + hisWindow < length) {
                preReadWindow = hisWindow;
            } else {
                preReadWindow = length - i;
            }

            // 字典缓冲区窗口字符
            String hisStr = dicStr.substring(i - hisWindow, hisWindow);
            // 预读缓冲区窗口字符
            String preReadStr = dicStr.substring(i, i + preReadWindow);
            // System.out.println(hisStr + " " + preReadStr);

            // 在字典缓冲区中寻找与预读缓冲区中的最匹配数据，循环截取预读缓冲区的前n个字符子串，
            // 查看字典缓冲区中是否包含预读缓冲区的前n个字符子串，直到截取预读缓冲区的前n个字符子串为空串
            String matchStr = "";
            while (true) {
                // 截取预读缓冲区的前n个字符子串为空串则退出
                if (preReadWindow <= 0) {
                    break;
                }
                // 截取预读缓冲区的前n个字符子串
                String substring = preReadStr.substring(0, preReadWindow);
                // 字典缓冲区中包含预读缓冲区的前n个字符子串 及是最匹配子串
                if (hisStr.contains(substring)) {
                    // 最佳匹配子串
                    matchStr = substring;
                    break;
                }
                // 不匹配继续往前截取子串
                preReadWindow--;
                // 截取预读缓冲区的前n个字符子串为空串则提前退出
                if (preReadWindow <= 0) {
                    break;
                }
            }

            StringBuffer sb = new StringBuffer();
            if (!"".equals(matchStr)) {
                // 存在最匹配子串
                // 匹配串在字典缓存中的最后的位置，用于计算最匹配子串开始偏移量
                int matchIndex = hisStr.lastIndexOf(matchStr);
                // 匹配的字符长度
                int matchStrLen = matchStr.length();
                // 预读缓冲区的字符长度
                int preReadStrLen = preReadStr.length();
                // 匹配串不是预读缓冲区字符串
                if (matchStrLen < preReadStrLen) {
                    // String nextChar = preReadStr.substring(matchStrLen, matchStrLen + 1);
                    // 长字符串中下一个待开始处理的字符
                    char nextChar = dicStr.charAt(i + matchStr.length());
                    // 字典缓冲区长度，用于计算最匹配子串的开始偏移量
                    int hisLen = hisStr.length();
                    // 数据拼接
                    sb.append("(").append(hisLen - matchIndex).append("," + matchStrLen).append("," + nextChar).append(")");
                    result.add(sb.toString());
                    // 将最匹配预读串中的子串加入字典缓冲区，即字典缓冲区窗口加上最匹配子串的长度
                    i += preReadWindow;
                } else {
                    // 最后的预读缓冲区的字符全部匹配情况需拼接匹配数据
                    int hisLen = hisStr.length();
                    sb.append("(").append(hisLen - matchIndex).append("," + matchStrLen).append("," + "").append(")");
                    result.add(sb.toString());
                    // 结束
                    break;
                }
            } else {
                // 不匹配预读下一个
                char nextChar = dicStr.charAt(i);
                sb.append("(").append(0).append("," + 0).append("," + nextChar).append(")");
                result.add(sb.toString());
            }
            // System.out.println(hisStr + " " + preReadStr + " -> " + sb.toString() + " " + i);
        }

        return result;
    }

    /**
     * 解压
     *
     * @param dicComStrList
     * @return
     */
    public static String dicUnCompress(List<String> dicComStrList) {
        String result = "";
        for (int i = 0; i < dicComStrList.size(); i++) {
            String comStr = dicComStrList.get(i);
            // 去除拼接数据的首尾()
            String curComDic = comStr.substring(1, comStr.length() - 1);
            String[] comStrArr = curComDic.split(",", -1);
            // 偏移量
            String pos = comStrArr[0];
            // 匹配长度
            String len = comStrArr[1];
            // 下一个字符
            String nextChar = comStrArr[2];
            if (pos.equals("0")) {
                // 不匹配
                result += nextChar;
            } else {
                // 匹配
                int length = result.length();
                // 最匹配子串开始偏移量
                int startI = length - Integer.valueOf(pos);
                // 最匹配子串结束偏移量
                int endI = startI + Integer.valueOf(len);
                // 截取得到最匹配子串进行拼接
                result += result.substring(startI, endI) + nextChar;
            }
        }

        return result;
    }
}
